import java.lang.invoke.WrongMethodTypeException;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-12
 * Time: 22:53
 */
public class Solution {

    public static int backPackII(int m, int[] a, int[] v) {
        // write your code here
        int row = a.length;
        int col = m; // 列表示空间的大小
        int[][] maxVal = new int[row+1][col+1];

        // 本身 new 出来的数组里面默认就是 0 , 所以就不用初始化了
//        for (int i = 0; i <= row ; i++) {
//            maxVal[i][0] = 0;
//        }
//
//        for (int i = 0; i <= col ; i++) {
//            maxVal[0][i] = 0;
//        }

        for (int i = 1; i <= row ; i++) {
            for (int j = 1; j <= col ; j++) {
                if(a[i - 1] <= j){
//                     物体能放到包中
//                     选择放与不放中的最大值
//                     其中放也包含了两种情况
//                     1. 本身剩余的空间就足够放
//                        maxVal[i-1][j] +　v[i]
//                     2. 本身剩余的空间不够, 需要腾出一些空间, 即拿出来一些物品
//                        maxVal[i-1][j - v[i]] + v[i]
//                     但其实第二种情况已经包含第一种了
//                     因为 本身空间就充足时,  maxVal[i-1][j - v[i]] == maxVal[i-1][j]
                    maxVal[i][j] = Math.max(maxVal[i-1][j - a[i - 1]] + v[i - 1], maxVal[i-1][j]);

                }else{
                    // 物体太大放不下
                    maxVal[i][j] = maxVal[i-1][j];
                }
            }
        }

        return maxVal[row][col];
    }

    public static int backPackII2(int m, int[] a, int[] v){
        // 使用滚动数组, 对空间进行优化
        int [] maxVal = new int[m + 1];
        // 不用初始化了
        for (int i = 1; i <= a.length ; i++) {
            // 特别注意这里 需要倒着修改, 因为更新的时候需要用到前面的值
            // 如果正着修改, 会使结果偏大
            for (int j = m; j > 0; j--) {
                if(a[i -1] <= j){
                    // 先得保证物体能放进背包中
                    maxVal[j] = Math.max(maxVal[j - a[i - 1]] + v[i - 1], maxVal[j]);
                }
                // 如果不能放进去, 直接不用修改即可
                // 直接使用得就是 上一行的值
            }
        }
        return maxVal[m];
    }

    public static void main(String[] args) {
        int m = 10;
        int[] a = {2,3,5,7};
        int[] v = {1,5,2,4};
        backPackII2(m, a, v);
        System.out.println();
    }
}
